'''
https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/description/
'''
from typing import List

class UnionFindSet:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.sets = n
    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]
    def is_same_set(self, i, j):
        return self.find(i) == self.find(j)
    def union(self, i, j):
        x, y = self.find(i), self.find(j)
        if x != y:
            self.father[x] = y
            self.sets -= 1

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        x_map = {}
        y_map = {}
        ufs = UnionFindSet(len(stones))
        for i, (x, y) in enumerate(stones):
            if x not in x_map:
                x_map[x] = i
            else:
                ufs.union(i, x_map[x])
            if y not in y_map:
                y_map[y] = i
            else:
                ufs.union(i, y_map[y])
        return len(stones) - ufs.sets

